/*
 * @Author: szx
 * @Date: 2022-05-17 13:46:51
 * @LastEditTime: 2022-05-17 14:20:11
 * @Description:
 * @FilePath: \leetcode\面试题\04\03\03.js
 */
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

function ListNode(val) {
    this.val = val;
    this.next = null;
}

/**
 * @param {TreeNode} tree
 * @return {ListNode[]}
 */
var listOfDepth = function (tree) {
    if (!tree) return [];
    let que = [tree],
        res = [];
    while (que.length) {
        const length = que.length;
        const arr = [];
        const node = new ListNode(que[0].val);
        que[0].left && arr.push(que[0].left);
        que[0].right && arr.push(que[0].right);
        let next = node;
        for (let i = 1; i < length; i++) {
            const tmp = new ListNode(que[i].val);
            next.next = tmp;
            next = next.next;
            que[i].left && arr.push(que[i].left);
            que[i].right && arr.push(que[i].right);
        }
        que = arr;
        res.push(node);
    }
    return res;
};

var listOfDepth = function (tree) {
    let res = [];
    let list = [tree];
    let nums = 1; // 保存下一轮循环需要遍历的节点个数
    while (list.length) {
        // 定义头节点
        let head = new ListNode(0);
        let temp = head;
        for (let i = 0; i < nums; i++) {
            // 先进先出
            let indexTree = list.shift();
            temp.next = new ListNode(indexTree.val);
            temp = temp.next;
            if (indexTree.left) list.push(indexTree.left);
            if (indexTree.right) list.push(indexTree.right);
        }
        nums = list.length;
        res.push(head.next);
    }
    return res;
};
